/*
 * =====================================================================================
 *
 *       Filename:  CStack.cpp
 *
 *    Description:  CStack.cpp
 *
 *         Author:  Younghyun Jo
 *   Organization:  Master Student
 *                  Computer Systems and Platforms Laboratory
 *                  Department of Computer Science and Engineering
 *                  Seoul National University
 *
 * =====================================================================================
 */

#include <cstdio>
#include <cstdlib>
#include "stack.h"

//--------------------------------------------------------------------------------------
// Node
//
// Node: This unbounded stack use doubly linked nodes
//

Node::Node()
  : _value(-1), _next(NULL), _prev(NULL)
{
}

Node::Node(const item_t value)
  : _value(value), _next(NULL), _prev(NULL)
{
}

Node::~Node()
{
}

//--------------------------------------------------------------------------------------
// CStack
//
// CStack: Basic implementation of CStack
//         It only supports one sequential task
//

CStack::CStack()
  : _head(NULL), _top(NULL)
{
}

CStack::~CStack(void)
{
  Node* node = _head;

  /* delete all entries */
  while (node != NULL) {
    Node* dnode = node;
    node = node->_next;
    delete dnode;
  }
}

bool CStack::Push(int value, int thread_id)
{
  Node* new_node = new Node(value);

  /* When the stack is empty */
  if (!_head) {
    // _head points to first node 
    // or we can use a sentinel node as a first node
    _head = new_node;
    new_node->_prev = _head;
  } else {
    _top->_next = new_node;
    new_node->_prev = _top;
  }

  _top = new_node;

  return true;
}

item_t CStack::Pop(void)
{
  /* When the stack is empty */
  if (!_head) {
    return NULL; // Exception
  } else {
    Node* pop_node = _top;
    _top = _top->_prev;
    return pop_node->_value;
  }
}

Node* CStack::Peek(void)
{
  return _top;
}

void CStack::Display(void)
{
  int i = 0;
  Node* node = _head;

  /* Display the entries */
  printf("Display the stack\n");
  while (node != NULL) {
    printf("[entry: %d, value: %d], ", i++, node->_value);
    node = node->_next;
  }

  printf("\n");
}

//--------------------------------------------------------------------------------------
// CCoarseGrainedLockStack
//
// CCoarseGrainedLockStack: It uses a coarse grained lock to preserve sequential order
//                          between a set of tasks
//

CCoarseGrainedLockStack::CCoarseGrainedLockStack()
{
  lock_init(&_lock); // init the basic spin lock
}

CCoarseGrainedLockStack::~CCoarseGrainedLockStack()
{
  lock_destruct(&_lock); // destruct the spin lock
}

bool CCoarseGrainedLockStack::Push(int value, int thread_id)
{
  Node* new_node = new Node(value);

  /* acquire the spin lock */
  lock_acquire(&_lock);

  /* When the stack is empty */
  if (!_head) {
    _head = new_node;
    new_node->_prev = _head;
  } else {
    _top->_next = new_node;
    new_node->_prev = _top;
  }

  _top = new_node;

  /* release the spin lock */
  lock_release(&_lock);

  return true;
}

item_t CCoarseGrainedLockStack::Pop(void)
{
  /* acquire the spin lock */
  lock_acquire(&_lock);

  /* When the stack is empty */
  if (!_head) {
    lock_release(&_lock); // Exception
    return NULL;
  } else {
    Node* pop_node = _top;
    _top = _top->_prev;

    /* release the spin lock */
    lock_release(&_lock);
    return pop_node->_value;
  }
}

//--------------------------------------------------------------------------------------
// CLockFreeStack
//
// CLockFreeStack: The implementation of Lock free stack by using compare and exch
//

CLockFreeStack::CLockFreeStack()
{
}

CLockFreeStack::~CLockFreeStack()
{
}

bool CLockFreeStack::Push(int value, int thread_id)
{
  Node* newNode = new Node(value);
  Node* oldTop = NULL; // it is for CompareAndSet in LockFreeStack
  int backoff = 2; // MIN_DELAY

  while (true) {
    oldTop = Peek();
    newNode->_prev = oldTop;

    /* TryPush(): CAS Lock free */
    if (arch_atomic_bool_compare_and_exchange(&_top, oldTop, newNode)) {
      //printf("Push:%lu\n", newNode->_value);
      return true;
    } else {
      /*  Back off to avoid spamming memory networks. */
      for (int i = backoff; i > 0; i--)
          __insn_mfspr(SPR_PASS);

      if (backoff < 256) // MAX_DELAY
          backoff *= 2;
    }
  }
}

item_t CLockFreeStack::Pop(void)
{
  Node* oldTop = NULL; // it is for CompareAndSet in LockFreeStack
                       // and, it will be also returning pop node
  int backoff = 2; // MIN_DELAY

  while (true) {
    oldTop = Peek();
    if (oldTop == NULL) return NULL; // Exception

    /* TryPop(): CAS Lock free */
    if (arch_atomic_val_compare_and_exchange(&_top, oldTop, oldTop->_prev)
        == oldTop) {
      //printf("Pop:%lu\n", oldTop->_value);
      return oldTop->_value;
    } else {
      /*  Back off to avoid spamming memory networks. */
      for (int i = backoff; i > 0; i--)
          __insn_mfspr(SPR_PASS);

      if (backoff < 256) // MAX_DELAY
          backoff *= 2;
    }
  }
}

//--------------------------------------------------------------------------------------
// CEliminationBackoffStack
//
// CEliminationBackoffStack: 
//

//--------------------------------------------------------------------------------------
CRangePolicy::CRangePolicy(int range)
  : _range(range), _success(0), _timeout(0)
{
}

CRangePolicy::~CRangePolicy()
{
  printf("  CEliminationBackoffStack Results::\n");
  printf("    Elimination Success: %lu\n", _success);
  printf("    Elimination TimeOut: %lu\n", _timeout);
}

int CRangePolicy::GetRange()
{
  return _range;
}

void CRangePolicy::RecordEliminationSuccess()
{
  _success++;
}

void CRangePolicy::RecordEliminationTimeout()
{
  _timeout++;
}

//--------------------------------------------------------------------------------------
CAtomicStampedReference::CAtomicStampedReference()
  : _item(NULL)
{
}

CAtomicStampedReference::~CAtomicStampedReference()
{
}

bool CAtomicStampedReference::CompareAndSet(item_t yrItem, item_t myItem,
                                            int beforeStamp, int nextStamp)
{
  /*
   * It mimics the AtomicStampedReference functionality in JAVA
   * This is used for changing two values (item, state) at the same time
   * and it can be also used to avoid ABA problem
   *
   * So, we can attack those spare area by using mask and bit operations
   * For the safety, we assume that the item will not be bigger than 2^62,
   * because we need at least two spare bits to contain the state value
   * (EMPTY, WAITING, and BUSY)
   *
   * Therefore, when the task take return pointer,
   * the task remove the stamp bits again.
   *
   * In this time, we don't consider ABA problem,
   * because it is negligable in this time.
   * but we can resolve the ABA problem also by using this kind of trick
   */

  item_t before = yrItem | ((item_t)(beforeStamp&0x03)<<62);
  item_t next = myItem | ((item_t)(nextStamp&0x03)<<62);

  if (arch_atomic_bool_compare_and_exchange(&_item, before, next)) {
    //printf("_item: %x before: %x next: %x\n", _item, before, next);
    return true;
  } else {
    return false;
  }
}

item_t CAtomicStampedReference::Get(int* stampHolder)
{
  stampHolder[0] = (int)(_item>>62)&0x03; // Get _state
  return _item & 0x3FFFFFFFFFFFFFFF; // Get _item, give the real Virtual Address
}

void CAtomicStampedReference::Set(item_t item, int newStamp)
{
  _item = item | ((item_t)(newStamp&0x03)<<62);
}

//--------------------------------------------------------------------------------------
long long CTimeUnit::GetTimeStamp(void)
{
  /* it returns current system time value as long long type */
  static __thread struct timeval tv;
  gettimeofday(&tv, NULL);
  return 1000000LL * tv.tv_sec + tv.tv_usec;
}

//--------------------------------------------------------------------------------------
CLockFreeExchanger::CLockFreeExchanger()
{
  _slot = new CAtomicStampedReference();
}

CLockFreeExchanger::~CLockFreeExchanger()
{
}

item_t CLockFreeExchanger::Exchange(item_t myItem, long long timeout, CTimeUnit* unit)
{
  /* timeBound = currentTimeStamp + timeOut */
  long long timeBound = unit->GetTimeStamp() + timeout;
  int stampHolder[] = {EMPTY};

  while (true) {
    if (unit->GetTimeStamp() > timeBound)
      throw TimeoutException();
    item_t yrItem = _slot->Get(stampHolder);
    int stamp = stampHolder[0];

    switch (stamp) {
      case EMPTY:
        /* Try to place the item in the slot and set the state to WAITING */
        if (_slot->CompareAndSet(yrItem, myItem, EMPTY, WAITING)) {
          while (unit->GetTimeStamp() < timeBound) { // within timeBound
            yrItem = _slot->Get(stampHolder);
            if (stampHolder[0] == BUSY) { // Another task shows up
              _slot->Set(NOITEM, EMPTY);
              return yrItem;
            }
          }
          // No other thread shows up, reset the state
          if (_slot->CompareAndSet(myItem, NOITEM, WAITING, EMPTY)) {
            throw TimeoutException();
          } else {
            yrItem = _slot->Get(stampHolder);
            _slot->Set(NOITEM, EMPTY);
            return yrItem;
          }
        }
        break;
      case WAITING:
        /* take the item, and try to replace it with its own by changing the state */
        if (_slot->CompareAndSet(yrItem, myItem, WAITING, BUSY))
          return yrItem;
        break;
      case BUSY:
        break;
      default: // impossible
        break;
    }
  }
}

//--------------------------------------------------------------------------------------
CEliminationArray::CEliminationArray(int capacity, long long timeout)
  : _duration(timeout), _random(new CRandom()), _timeUnit(new CTimeUnit()), 
    _capacity(capacity)
{
  exchanger = (CLockFreeExchanger**)malloc(capacity*sizeof(CLockFreeExchanger*));
  for (int i=0; i<capacity; i++)
    exchanger[i] = new CLockFreeExchanger();
}

CEliminationArray::~CEliminationArray()
{
  for (int i=0; i<_capacity; i++)
    delete exchanger[i];
}

item_t CEliminationArray::visit(item_t item, int range)
{
  int slot = _random->nextInt(range);
  return (exchanger[slot]->Exchange(item, _duration, _timeUnit));
}

//--------------------------------------------------------------------------------------
CEliminationBackoffStack::CEliminationBackoffStack()
  : _capacity(16), _timeout(1000LL) // default: 16 entries, 1 micro second timeout
{
  _rangePolicy = new CRangePolicy(_capacity);
  _eliminationArray = new CEliminationArray(_capacity, _timeout);
}

CEliminationBackoffStack::CEliminationBackoffStack(int capacity, long long timeout)
  : _capacity(capacity), _timeout(timeout)
{
  _rangePolicy = new CRangePolicy(_capacity);
  _eliminationArray = new CEliminationArray(_capacity, _timeout);
}

CEliminationBackoffStack::~CEliminationBackoffStack()
{
  delete _eliminationArray;
  delete _rangePolicy;
}

bool CEliminationBackoffStack::Push(int value, int thread_id)
{
  Node* node = new Node(value);

  while (true) {
    Node* oldTop = Peek();
    node->_prev = oldTop;

    /* Try Push */
    if (arch_atomic_bool_compare_and_exchange(&_top, oldTop, node)) {
      return true;
    } else {
      /* If it fails, visit the elimination array */
      try {
        item_t item = _eliminationArray->visit(node->_value, _rangePolicy->GetRange());
        if (item == NOITEM) {
          //printf("Elimination success! push: %lu\n", node->_value);
          _rangePolicy->RecordEliminationSuccess();
          return true; // exchanged with pop
        }
      } catch (TimeoutException ex) {
        //printf("Elimination timeout! push: %lu\n", node->_value);
        _rangePolicy->RecordEliminationTimeout();
      }
    }
  }
}

item_t CEliminationBackoffStack::Pop(void)
{
  while (true) {
    Node* oldTop = Peek();
    if (oldTop == NULL) return NULL;

    /* Try Pop */
    if (arch_atomic_val_compare_and_exchange(&_top, oldTop, oldTop->_prev == oldTop)) {
      return oldTop->_value;
    } else {
      try {
        /* If it fails, visit the elimination array */
        item_t item = _eliminationArray->visit(NOITEM, _rangePolicy->GetRange());
        if (item != NOITEM) {
          //printf("Elimination success! pop: %lu\n", item);
          _rangePolicy->RecordEliminationSuccess();
          return item; // exchanged with push
        }
      } catch (TimeoutException ex) {
        //printf("Elimination timeout!\n");
        _rangePolicy->RecordEliminationTimeout();
      }
    }
  }
}

//--------------------------------------------------------------------------------------
// CCombTreeStack
//
// CCombTreeStack: The implementation of stack which uses combining tree to reduce
//                 the memory contention
//


//--------------------------------------------------------------------------------------
TreeInput::TreeInput(Node* node)
  : _prev(NULL),
    _next(NULL),
    _node(node)
{
  if (node == NULL) _oper = POP; // Pop operation
  else _oper = PUSH;
}

TreeInput::~TreeInput()
{
  //delete this;
}

CTreeInputList::CTreeInputList()
  : _headPush(NULL),
    _topPush(NULL),
    _headPop(NULL),
    _topPop(NULL)
{
}

CTreeInputList::CTreeInputList(TreeInput* input)
{
  if (input->IsPush()) {
    _headPush = input;
    _topPush = input;
    _headPop = NULL;
    _topPop = NULL;
    input->_prev = _headPush;
    input->_next = NULL;
  } else if (input->IsPop()) {
    _headPop = input;
    _topPop = input;
    _headPush = NULL;
    _topPush = NULL;
    input->_prev = _headPop;
    input->_next = NULL;
  }
}

CTreeInputList::~CTreeInputList()
{
}

//--------------------------------------------------------------------------------------
TreeNode::TreeNode()
  : _locked(false),
    _cStatus(ROOT),
    _firstValue(NULL),
    _secondValue(NULL),
    _result(NULL),
    _parent(NULL)
{
  spin_lock_init(&_nodeLock);
  cond_lock_init(&_cond);
}

TreeNode::TreeNode(TreeNode* myParent)
  : _locked(false),
    _cStatus(IDLE),
    _firstValue(NULL),
    _secondValue(NULL),
    _result(NULL),
    _parent(myParent)
{
  spin_lock_destruct(&_nodeLock);
  cond_lock_destruct(&_cond);
}

TreeNode::~TreeNode()
{
  //delete this;
}

TreeNode* TreeNode::GetParent()
{
  return _parent;
}

bool TreeNode::PreCombine()
{
  //printf("precombine::\n");
  ScopeLock l(&_nodeLock); // synchronized method

  while (_locked) {
    cond_lock_wait(&_cond, &_nodeLock);
  }

  switch(_cStatus) {
    case IDLE:
      _cStatus = FIRST;
      return true;
    case FIRST:
      _locked = true;
      _cStatus = SECOND;
      return false;
    case ROOT:
      return false;
    default:
      printf("unexpected node state, precombine\n");
      exit(1);
  }
}

CTreeInputList* TreeNode::Combine(CTreeInputList* combined)
//int TreeNode::Combine(int combined)
{
  //printf("combine::\n");
  ScopeLock l(&_nodeLock);

  while (_locked) {
    cond_lock_wait(&_cond, &_nodeLock);
  }

  _firstValue = combined;
  _locked = true;
  switch (_cStatus) {
    case FIRST:
      return _firstValue;
    case SECOND:
      return Merge(_firstValue, _secondValue);
    default:
      printf("unexpected node state, combine\n");
      exit(1);
  }
}

CTreeInputList* TreeNode::Op(CTreeInputList* combined)
//int TreeNode::Op(int combined)
{
  //printf("op::\n");
  ScopeLock l(&_nodeLock);

  CTreeInputList* oldList;

  switch (_cStatus) {
    case ROOT:
      oldList = _result;
      _result = Merge(_result, combined);
      return oldList;
    case SECOND:
      _secondValue = combined;
      _locked = false;
      cond_lock_signalAll(&_cond);
      while (_cStatus != RESULT)
        cond_lock_wait(&_cond, &_nodeLock);
      _locked = false;
      cond_lock_signalAll(&_cond);
      _cStatus = IDLE;
      return _result;
    default:
      printf("unexpected op\n");
      exit(1);
  }
}

void TreeNode::Distribute(CTreeInputList* prior)
//void TreeNode::Distribute(int prior)
{
  //printf("dist::\n");
  ScopeLock l(&_nodeLock);

  switch (_cStatus) {
    case FIRST:
      _cStatus = IDLE;
      _locked = false;
      break;
    case SECOND:
      _result = Merge(prior, _firstValue);
      _cStatus = RESULT;
      break;
    default:
      printf("unexpected distribute\n");
      exit(1);
  }

  cond_lock_signalAll(&_cond);
}

CTreeInputList* TreeNode::Merge(CTreeInputList* first, CTreeInputList* second)
{
  //printf("try merge!\n");
  if (first == NULL && second != NULL) { return second; }
  else if (first != NULL && second == NULL) { return first;}
  else if (first == NULL && second == NULL) { return NULL; }

  CTreeInputList* merge = new CTreeInputList();
  
  /* merge push lists */
  if (first->_headPush != NULL && second->_headPush == NULL) {
    merge->_headPush = first->_headPush;
    merge->_topPush = first->_topPush;
  } else if (first->_headPush == NULL && second->_headPush != NULL) {
    merge->_headPush = second->_headPush;
    merge->_topPush = second->_topPush;
  } else if (first->_headPush == NULL && second->_headPush == NULL) {
    merge->_headPush = NULL;
    merge->_topPush = NULL;
  } else {
    merge->_headPush = first->_headPush;
    first->_topPush->_next = second->_headPush;
    second->_headPush->_prev = first->_topPush;
    merge->_topPush = second->_topPush;
  }

  /* merge pop lists */
  if (first->_headPop != NULL && second->_headPop == NULL) {
    merge->_headPop = first->_headPop;
    merge->_topPop = first->_topPop;
  } else if (first->_headPop == NULL && second->_headPop != NULL) {
    merge->_headPop = second->_headPop;
    merge->_topPop = second->_topPop;
  } else if (first->_headPop == NULL && second->_headPop == NULL) {
    merge->_headPop = NULL;
    merge->_topPop = NULL;
  } else {
    merge->_headPop = first->_headPop;
    first->_topPop->_next = second->_headPop;
    second->_headPop->_prev = first->_topPop;
    merge->_topPop = second->_topPop;
  }

  //return merge;

  /* elimination the duplications between push and pop */
  TreeInput* push = merge->_headPush;
  TreeInput* pop = merge->_headPop;

  //printf("try elimination!\n");
  while (true) {
    if (push == NULL || pop == NULL) {
      /* no matching operations any more */
      //printf("no matching operations at this time\n");
      break;
    } else {
      /*
       * eliminate one operation
       * the current push and pop operation is going to be eliminated, however
       * we do not handle returning node to reduce extra overheads.
       * we just measure the performance of concurrent stack
       */
      merge->_headPush = push->_next;
      merge->_headPop = pop->_next;
      push->_next->_prev = merge->_headPush;
      pop->_next->_prev = merge->_headPop;

      // need to delete this
      //printf("elimination occurs, pop: %lu\n", push->_node->_value);

      /* point to next operation */
      push = push->_next;
      pop = pop->_next;
    }
  }

  return merge;
}

//--------------------------------------------------------------------------------------
CCombTreeStack::CCombTreeStack(int size)
  : _treeSize(size-1)
{
  _nodes = new TreeNode*[size-1];
  _nodes[0] = new TreeNode();
  for (int i=1; i<size-1; i++) {
    _nodes[i] = new TreeNode(_nodes[(i-1)/2]); // parent
  }

  _leaf = new TreeNode*[(size+1)/2];
  for (int i=0; i<(size+1)/2; i++) {
    _leaf[i] = _nodes[size-1 -i -1];
  }
}

CCombTreeStack::~CCombTreeStack()
{
  for (int i=0; i<_treeSize; i++)
    delete _nodes[i];

  delete []_leaf;
  delete []_nodes;
}

bool CCombTreeStack::Push(int value, int thread_id)
{
  Node* newNode = new Node(value);
  CTreeInputList* list = new CTreeInputList(new TreeInput(newNode));
  list = VisitTree(thread_id, list);
}

item_t CCombTreeStack::Pop(int thread_id)
{
  Node* popNode = new Node(); // popNode does not contain initial value
  CTreeInputList* list = new CTreeInputList(new TreeInput(popNode));
  list = VisitTree(thread_id, list);
}

#include <list>
CTreeInputList* CCombTreeStack::VisitTree(int thread_id, CTreeInputList* input)
{
  std::list <TreeNode*> path;
  TreeNode* myLeaf = _leaf[thread_id/2];
  TreeNode* node = myLeaf;

  // precombining phase
  while (node->PreCombine()) {
    node = node->GetParent();
  }

  TreeNode* stop = node;

  // combining phase
  node = myLeaf;
  CTreeInputList* combined = input;
  while (node != stop) {
    combined = node->Combine(combined);
    path.push_back(node);
    node = node->GetParent();
  }

  // operation phase
  CTreeInputList* prior = stop->Op(combined);

  // distribute phase
  while (!path.empty()) {
    node = path.back();
    path.pop_back();
    node->Distribute(prior);
  }

  return prior;
}

